NC Milling
Simulating the process of numerically controlled (NC) milling is of fundamental importance in computer aided design (CAD) and computer aided manufacturing (CAM). During simulation, a computer model of a workpiece is edited with a computer representation of an NC milling tool and a set of NC milling tool motions to simulate the milling process.
The workpiece model and tool representation can be visualized during the simulation to detect potential collisions between parts, such as the workpiece and the tool holder, and after the simulation to verify the final shape of the workpiece.
The final shape of the workpiece is affected by the selection of the tool and the tool motions. Instructions for controlling these motions are typically generated using a computer aided manufacturing system from a graphical representation of the desired final shape of the workpiece. The motions are typically implemented using numerical control programming language, also known as preparatory code or G-Codes, see the following standards RS274D and DIN 66025/ISO 6983.
The G-Codes generated by the computer aided manufacturing system may not produce an exact replication of the desired shape. In addition, the movement of the NC tool is governed by motors of the NC milling machine, which have limited speeds, ranges of motion, and abilities to accelerate and decelerate, so that the actual tool motions may not exactly follow the NC machine instructions.
Discrepancies between the actual final shape of the workpiece and the desired shape of the workpiece may be very small. In some situations, these discrepancies can result in undesirable gouges or nicks in the surface of the final shape of the workpiece with sizes on the order of a few micrometers in depth and width, and tens of micrometers in length.
Typically, a set of NC machine instructions is tested by milling a test workpiece made of softer, less expensive material prior to milling the desired part. If visual inspection of the test workpiece locates undesirable discrepancies in the test workpiece, the NC machine instructions can be modified accordingly.
This manual testing is time consuming and expensive. Time for machining a single test workpiece may be on the order of hours and several iterations may be required before an acceptable set of NC machine instructions is attained. Thus, it is desirable to test for these discrepancies using computer-based simulation and rendering. However, in order to detect discrepancies with dimensions on the order of a few micrometers for workpieces, which may have dimensions on the order of one meter, very precise computer models are required. It is an object of the present invention to provide a space and time efficient method for representing and rendering such high precision models for milling simulation.
Swept Volumes
During milling, a tool moves relative to the workpiece according to a prescribed tool motion, referred to herein as a tool path, where the tool path can contain information about the relative position, orientation, and other shape data of the tool with respect to the workpiece.
As the tool moves along the tool path, the tool carves out a “swept volume.” During milling, as the tool moves along the tool path, a portion of the workpiece that is intersected by the swept volume is removed. This material removal can be modeled in the computer as a constructive solid geometry (CSG) difference operation, in which the portion of the workpiece is removed from the workpiece using a CSG subtraction operation of the swept volume from the workpiece.
In order to provide high precision milling simulation, it is necessary to have a precise representation of the swept volume. Thus, it is an object of the present invention to provide a space and time efficient method for representing and rendering high precision models of swept volumes.
Although NC milling simulation is used as an example herein, swept volumes have applications in many areas of science, engineering, entertainment, and computer graphics. Some specific applications include computer-aided design, freeform design, computer-based drawing, animation, solid modeling, robotics, manufacturing automation, and visualization to name but a few. The following description applies to all areas where an accurate representation of a swept volume is required or desired.
Although we focus here on three-dimensional coordinate systems, the term ‘swept volume’ can be extended more generally to N-dimensional coordinate systems. In particular, the following discussion also applies to areas swept out by a one-dimensional or two-dimensional shape moving along a path in a two-dimensional space or to a hyper-volume swept out by a shape moving over a path or surface in higher dimensional spaces.
We begin with a review of prior art in the field of the invention. An overview of the importance and challenges in swept volume research is presented in “Swept Volumes: Foundations, Perspectives, and Applications”, International Journal of Shape Modeling, 2006, Abdel-Malek, Blackmore, and Joy. They conclude that research in this field is limited by the difficulty of implementing complex mathematical formulations of sweeps in computer software and that computing the boundaries of swept volumes remains a challenging problem requiring better visualization tools and more accurate methods.
The swept volumes of simple shapes moving along simple paths can sometimes be represented analytically, as described in U.S. Pat. No. 4,833,617. However, those methods do not generalize to complex shapes and complex tool paths.
Several approaches approximate the swept volumes of polygonal shapes. Models of polygonal shapes can be encoded in a spatial hierarchy for efficient editing via CSG operations as in “Interactive CSG” Proceedings, Technical Sketches, SIGGRAPH, 1999, Butcher, or for efficient collision detection as in U.S. Pat. No. 6,099,573.
A method for approximating the swept volume of a polygonal object is described in “Computing Swept Volumes”, Journal of Visualization and Animation, 2000, Abrams and Allen.
U.S. Pat. No. 6,862,560 describes a method for simulating machining using CSG operations on polygonal models of swept volumes. In that method, the boundary of the workpiece is encased in a set of cells, where each cell contains references to swept volume polygons that intersect the cell. Intersections between the workpiece and the swept volume polygons within a particular cell can be processed on demand to generate a high precision rendering of the milled surface in a small region of interest. However, visualizing the full model at high precision is prohibitively slow. In addition, the generation of the swept volumes and the processing of the intersections are not described.
U.S. Pat. No. 6,993,461 describes representing an object as a polyhedron. The object is placed along the path at discrete time steps using a series of transformations. Edges and faces of the polyhedral representation that lie on the boundary of the swept volume are determined at each time step and connected to generate a polyhedral approximation of the swept volume.
The accuracy of each of these polygonal methods is limited by the polygonal representation of the object model. Billions of polygons may be required to accurately represent the curved surface of a complex tool, especially if the radius of curvature is small. Thus, those methods either have limited accuracy or they have prohibitive processing times and memory requirements for generating high precision models of swept volumes or both. In addition, methods that approximate the swept volume as a series of discrete time steps have limited precision between the time steps, and are subject to aliasing artifacts.
Another common representation for milling simulation is known as the Z-buffer or Dexel method. That approach is described in “Real-time Shaded NC Milling Display”, Proceedings, SIGGRAPH 1986, van Hook. U.S. Pat. No. 7,149,668 describes a similar method in which the workpiece is modeled by a grid of straight lines all in the z-direction and the milling simulation is performed by moving the tool model over the grid and modifying the height of the lines representing the workpiece that are intersected by the tool.
Dexel methods typically suffer from limited resolution, especially in directions not aligned with the z-axis, and are not suitable for generating high precision models of swept volumes.
Dexel representations are related to voxel-based representations. In “Volume Visualization”, IEEE Computer Society Press, 1991, Kaufman describes voxel-based representations as well as methods for rendering and processing voxel-based representations. “Sculpting: an Interactive Volumetric Modeling Technique”, Proceedings, SIGGRAPH 1991, Galyean and Hughes, and “Volume Sculpting: Proceedings, SIGGRAPH 1995, Wang and Kaufman, both simulate sculpting using CSG operations on voxel-based representations of objects.
Methods that use binary voxels to represent swept volumes include U.S. Pat. No. 6,044,306, and “Method and Apparatus for Shaping Geometric Shapes” and “Octree-based Boundary Evaluation for General Sweeps”, Proceedings, TMCE, 2008 Erdim and Ilies. These methods both have accuracy limited by the size of the smallest voxel used to represent the swept volumes.
Distance Fields
Distance fields are an effective representation for rendering and editing shapes, as described in U.S. Pats. No. 6,396,492, 6,724,393, 6,826,024, and 7,042,458.
Distance fields are a form of implicit functions, which have been used to represent and render swept volumes. “Sweeping of Three Dimensional Objects”, Computer Aided Design, 20(4), 1990, Martin and Stephenson, described a theoretical foundation for defining the envelope of a swept volume in terms of an implicit function. In “Function Representation for Sweeping by a Moving Solid”, Proceedings, Solid Modeling, 1995, Sourin and Pasko represented swept volumes using implicit surfaces. However, implicit surfaces can be difficult to render, and a suitable implicit representation for an arbitrarily complex tool shape is difficult to define.
Adaptively sampled distance fields (ADFs) use detail-directed sampling to provide a space and time efficient representation of distance fields. ADFs store the distance field in a spatial hierarchy of cells. Each cell contains distance data and a reconstruction method for reconstructing the portion of the distance field associated with the cell. Distance data can include the value of the distance field, as well as the gradient and partial derivatives of the distance field. The distance field within a cell can be reconstructed only when needed to save memory and computation.
ADFs can be used to simulate editing using CSG operations. The model to be edited and the editing tool can be represented as distance functions, regularly sampled distance fields, or ADFs. The editing process can generate an ADF of the edited shape explicitly, for example by modifying an ADF of the model. Alternatively, the edited shape can be represented implicitly as a composite ADF. The composite ADF stores distance fields of the model and the editing tool, operators corresponding to the distance fields, such as a CSG subtraction operator for the editing tool, and a distance field reconstruction method that combines the stored distance fields on demand during rendering or other processing.
U.S. Pat. No. 6,724,393 describes a method for editing an ADF with a swept volume corresponding to the geometry of the tool as the tool moves along a curved path. The method determines the distance from a sample point to the path, and then uses the tool geometry to determine the distance to the surface of the tool. However, the method does not provide an accurate representation of the distance field for shapes that are not spherically symmetric and it is not suitable for high precision modeling.
The reconstruction method used to reconstruct the distance field within each ADF cell can be specified on a per cell basis and can be specialized to surface features within the cell such as sharp edges and corners. Specialized reconstruction methods can be used to improve the accuracy of the ADF representation near such features.
In “Feature sensitive surface extraction from volume data”, Proceedings, SIGGRAPH 2001, Kobbelt, Botsch, Schwaneke, and Seidel, described an alternate method to improve the accuracy of traditional sampled distance field representations. In that method, the x, y, and z distances to the closest intersections between the shape boundary and the sampling grid in the corresponding positive x, y, and z directions are stored at each sample point. That method can be used to reconstruct more accurate surface models from the sampled data using a modified version of Marching Cubes.
In “Complete Distance Field Representation”, Proceedings, IEEE Visualization, 2001, Huang, Li, Crawfis, and Lu augmented the traditional sampled distance field representation to enable more precise reconstruction of the object boundary and offset surfaces of the object. Either regularly or adaptively sampled distance fields can be used. References to polygons that may affect the object boundary or interior offset surfaces are stored within each cell, thus making it possible to compute distances to the polygonal surface model accurately. However, the rendered surface is reconstructed and rendered using point models, with points in the point model located at the center of cells containing the rendered surface. Thus, the accuracy of the final surface is limited by the resolution of the boundary cells.
Distance fields have been used to represent swept volumes. U.S. Pat. No. 5,542,036 represents both the tool shape and the swept volume as regularly sampled distance fields. The swept volume is constructed by transforming the regularly sampled distance field of the tool to a set of discrete positions along the tool path. The distance field of the tool is reconstructed at each sample point of the swept volume for each tool position, and performing a CSG union of the reconstructed distances at each sample point. A triangle model of the surface of the swept volume is reconstructed using Marching Cubes, Lorensen and Cline, “Marching Cubes: A high resolution 3D surface construction algorithm,” Computer Graphics, Vol. 21, Nr. 4, July 1987. The accuracy of the swept volume is limited by the resolution of the regularly sampled distance fields of the tool and the swept volume and by the discrete sampling of the tool path.
In “Fast Swept Volume Approximation of Complex Polyhedral Models”, Proceedings, Shape Modeling, 2003, Kim, Varadhan, Lin, and Manocha described an approach for approximating the swept volume of a complex object. In that approach, complex objects are approximated with a polygonal approximation. Unsigned distances to polygons in the approximation are computed on a regular grid and then post-processed to determine signed distances. The iso-surface of the sampled distance field is reconstructed to determine the boundary of the swept volume. In that approach, the accuracy is limited by the polygonal approximation of the surface primitives, and by the resolution of the distance grid.
None of the methods described above can provide the resolution required for representing high precision swept volumes of arbitrary shapes. Those methods are limited by the spatial resolution of the representation of the shapes and the swept volumes and by a discrete sampling of the tool path to approximate the tool motion.
In “Function Representation for Sweeping by a Moving Solid”, Proceedings, Solid Modeling, 1995, Sourin and Pasko used an implicit representation of the tool and the swept volume to provide and accurate representation of curved surfaces and attempts to reduce artifacts due to sampling the tool path. The implicit representation of the swept volume is defined as the CSG union of the implicit representation of the tool transformed to a discrete set of points along the tool path corresponding to a discrete set of N sampled times t0, t1, . . . tN−1 along the path.
In that approach, the value of the implicit function of the swept volume at a sample point is approximated in a “discrete manner.” First, the implicit representation of the tool is transformed to a set of positions corresponding to the N sampled times t0, t1, . . . tN−1 along the path and evaluated at the sample point to determine a sampled value for each position. A pair of sampled times ti and ti+1, that bracket an optimal time along the tool path when the tool is closest to the sample point, are determined, and either 1) a pair of sampled values corresponding to the sampled times ti and ti+1 are blended together, or 2) the sampled times ti and ti+1 are blended to compute an approximation of the optimal time t, the implicit representation of the tool is transformed to a point along the tool path corresponding to t, and the transformed implicit representation of the tool is evaluated at the sample point.
Most of the computation in that approach is spent evaluating the transformed implicit function for each time along the path. Because the value of the implicit function at each sample point is evaluated in a discrete manner, an accurate approximation of the swept volume requires that N be very large. Thus, the transformed implicit representation of the tool must be evaluated many times for each sample point. Although that method can provide a high precision model of the swept volume, it is prohibitively slow and has not been generally adopted in practice.
Thus, there is a need for a space and time efficient method for generating a high precision representation of a swept volume generated by moving an arbitrary shape along an arbitrary path whose precision is not limited by the shape representation or a discrete sampling of the tool path. Further, there is a need for a space and time efficient NC milling simulation system that can represent undesirable features with sizes on the order of a few micrometers in a workpiece with dimensions on the order of one meter.